/*
* srm 181 div 1 prob 3
*/

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;


public class KiloManX
{
	int N;
	int[][] d;
	int[] v;
	
	void check (int x) {
		if (x == (1<<(N+1)) - 1) {
			v[x] = 0;
			return;
		}
		if (v[x] != Integer.MAX_VALUE)
			return;
		for (int i = 0; i <= N; ++i) {
			if ((x & (1<<i)) == 0) continue;
			for (int j = 0; j <= N; ++j) {
				if ((x & (1<<j)) != 0) continue;
				if (d[i][j] == Integer.MAX_VALUE) continue;
				
				int y = x | (1<<j);
				check (y);
				v[x] = Math.min(v[x], d[i][j] + v[y]);
			}
		}
		return;
		
	}
	
	public int leastShots(String[] damageChart, int[] bossHealth)
	{
		N = bossHealth.length;
		d = new int[N+1][N+1];
		/* Root is N. Bosses are 0~N-1. */
		for (int i = 0; i <= N; ++i)
			for (int j = 0; j <= N; ++j)
				d[i][j] = Integer.MAX_VALUE;
		for (int i = 0; i < N; ++i)
			d[N][i] = bossHealth[i];
		for (int i = 0; i < N; ++i)
			for (int j = 0; j < N; ++j) {
				if (i == j) continue;
				int da = damageChart[i].charAt(j) - '0';
				if (da == 0) continue;
				d[i][j] = (bossHealth[j] + da - 1)/da;
			}
	
		v = new int[1<<(N+1)];
		Arrays.fill(v, Integer.MAX_VALUE);
		check (1<<N);
		return v[1<<N];
	}
	
	// BEGIN KAWIGIEDIT TESTING
	// Generated by KawigiEdit 2.1.4 (beta) modified by pivanof
	private static boolean KawigiEdit_RunTest(int testNum, String[] p0, int[] p1, boolean hasAnswer, int p2) {
		System.out.print("Test " + testNum + ": [" + "{");
		for (int i = 0; p0.length > i; ++i) {
			if (i > 0) {
				System.out.print(",");
			}
			System.out.print("\"" + p0[i] + "\"");
		}
		System.out.print("}" + "," + "{");
		for (int i = 0; p1.length > i; ++i) {
			if (i > 0) {
				System.out.print(",");
			}
			System.out.print(p1[i]);
		}
		System.out.print("}");
		System.out.println("]");
		KiloManX obj;
		int answer;
		obj = new KiloManX();
		long startTime = System.currentTimeMillis();
		answer = obj.leastShots(p0, p1);
		long endTime = System.currentTimeMillis();
		boolean res;
		res = true;
		System.out.println("Time: " + (endTime - startTime) / 1000.0 + " seconds");
		if (hasAnswer) {
			System.out.println("Desired answer:");
			System.out.println("\t" + p2);
		}
		System.out.println("Your answer:");
		System.out.println("\t" + answer);
		if (hasAnswer) {
			res = answer == p2;
		}
		if (!res) {
			System.out.println("DOESN'T MATCH!!!!");
		} else if ((endTime - startTime) / 1000.0 >= 2) {
			System.out.println("FAIL the timeout");
			res = false;
		} else if (hasAnswer) {
			System.out.println("Match :-)");
		} else {
			System.out.println("OK, but is it right?");
		}
		System.out.println("");
		return res;
	}
	public static void main(String[] args) {
		boolean all_right;
		all_right = true;
		
		String[] p0;
		int[] p1;
		int p2;
		
		// ----- test 0 -----
		p0 = new String[]{"070","500","140"};
		p1 = new int[]{150,150,150};
		p2 = 218;
		all_right = KawigiEdit_RunTest(0, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 1 -----
		p0 = new String[]{"1542","7935","1139","8882"};
		p1 = new int[]{150,150,150,150};
		p2 = 205;
		all_right = KawigiEdit_RunTest(1, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 2 -----
		p0 = new String[]{"07","40"};
		p1 = new int[]{150,10};
		p2 = 48;
		all_right = KawigiEdit_RunTest(2, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 3 -----
		p0 = new String[]{"198573618294842","159819849819205","698849290010992","000000000000000","139581938009384","158919111891911","182731827381787","135788359198718","187587819218927","185783759199192","857819038188122","897387187472737","159938981818247","128974182773177","135885818282838"};
		p1 = new int[]{157,1984,577,3001,2003,2984,5988,190003,9000,102930,5938,1000000,1000000,5892,38};
		p2 = 260445;
		all_right = KawigiEdit_RunTest(3, p0, p1, true, p2) && all_right;
		// ------------------
		
		// ----- test 4 -----
		p0 = new String[]{"02111111","10711111","11071111","11104111","41110111","11111031","11111107","11111210"};
		p1 = new int[]{28,28,28,28,28,28,28,28};
		p2 = 92;
		all_right = KawigiEdit_RunTest(4, p0, p1, true, p2) && all_right;
		// ------------------
		
		if (all_right) {
			System.out.println("You're a stud (at least on the example cases)!");
		} else {
			System.out.println("Some of the test cases had errors.");
		}
	}
	// END KAWIGIEDIT TESTING
}
